There Is No Preview Available For This Item
This item does not appear to have any files that can be experienced on Archive.org.
Please download files in this item to interact with them on your computer.
Show all files
The multiple intents re-ranking problem was introduced recently by Azar, Gamzu and Xin (STOC 2009) in the context of ordering results of a web search query. In this problem, we are given a universe of elements U and a collection of subsets S1,S2,..,Sm.
Additionally, each set S has a covering requirement of K(S).
The goal is to order the elements in U to minimize average covering time of a set, where set S is said to be covered at time t, if t is the earliest time at which K(S) elements from S appear in the ordering.
This problem generalizes various problems: (i) If
K(S) = 1 for all sets, we get the min-sum set cover problem, and (ii) If K(S) = |S| for all sets, we get the minimum-latency set cover problem. Recently, Azar et al. gave an elegant logarithmic approximation algorithm for this problem. They also gave O(1) approximations for some special cases.
In this talk, I will describe an O(1) approximation for the general problem.
Our result is based on formulating and rounding a strengthened LP relaxation of the problem based on the so-called Knapsack Cover Inequalities.
This is joint work with Ravishankar Krishnaswamy and Anupam Gupta.